\chapter{Experimental Results}

This section describes the results that we obtained using the tool MDParser, we developed to extract RTL patterns from MD files. Recall that
patterns are obtained by extracting the form of the RTL templates.

The Machine description files of five machines

\begin{enumerate}
 \item ARM
 \item i386
 \item MIPS
 \item SPARC
 \item VAX
\end{enumerate}

were considered for the results enumerated below. These files are taken from the back-end of GCC version 4.6.1. 

\section{Extracting Patterns From MD Files}
Table \ref{tab:Pat&Templates} lists the number of RTL templates considered in each of the machine's machine description 
file and the number of patterns that form the basis of it.

\begin{table}[h]
 \centering
\begin{tabular}{|c | c | c|}
\hline
Machine & No. of Templates & No. of Patterns \\
\hline
ARM & 1581 & 362\\
\hline
i386 & 2238 & 547\\
\hline
MIPS & 736 & 209\\
\hline
SPARC & 701 & 187\\
\hline
VAX & 125 & 64\\
\hline
\end{tabular}
\caption{Summary of Patterns and RTL Templates}
\label{tab:Pat&Templates}
\end{table}

From table\ref{tab:Pat&Templates} it is observed that in general, the number of patterns are around one fourth of the number of
templates within a given machine description. This tells us about the level of redundancy that is present within 
machine description files. For example, ARM has 1581 RTL templates, but only 362 patterns.


\section{Common Patterns Between Machines}

Table \ref{tab:Inter1} lists the number of patterns that are common between the machines. This was obtained by performing
an intersection of the pattern files extracted from each machines after parsing.
\begin{table}[htb!]
 \centering
\begin{tabular}{|c | c | c| c | c | c |}
\hline
 & Arm & I386 & Mips & Sparc & Vax \\
\hline
Arm &  & 101 & 75 & 79 & 35\\
\hline
I386 & 101 &  & 73 & 63 & 34\\
\hline
Mips & 75 & 73 & & 48 & 29 \\
\hline
Sparc & 79 & 63 & 48 & & 30\\
\hline
Vax & 35 & 34 & 29 & 30 & \\
\hline
\end{tabular}
\caption{Common Patterns}
\label{tab:Inter1}
\end{table}


Suppose we have a pattern p from machine m1 which matches
with pattern p from machine m2. Let c\textsubscript{i} be the count associated with p of m1
 and c\textsubscript{j} be the count associated with p of m2.
There are a total c\textsubscript{i} + c\textsubscript{j}  templates in the machines m1 and m2 sharing the
same pattern p\textsubscript{i}(or p\textsubscript{j}). This is listed in table \ref{tab:Inter2}.

% \begin{table}[htb!]
%  \centering
% \begin{tabular}{|c | p{3cm} | p{3cm}| p{3cm} | p{3cm} | p{3cm} |}
% \hline
%  (n1+n2)& Arm & I386 & Mips & Sparc & Vax \\
% \hline
% Arm &  & (2281/3819)\newline=59.72\% & (1486/2317)\newline=64.13\% & (1475/2282)\newline=64.63\% & (799/1706)\newline=46.83\%\\
% \hline
% I386 & (2281/3819)\newline=59.72\% &  & (1584/2974)\newline=53.26\% & (1441/2939)\newline=49.03\% & (719/2363)\newline=30.42\%\\
% \hline
% Mips & (1486/2317)\newline=64.13\% & (1584/2974)\newline=53.26\% & & (838/1437)\newline=58.31\% & (355/861)\newline=41.23\% \\
% \hline
% Sparc & (1475/2282)\newline=64.63\% & (1441/2939)\newline=49.03\% & (838/1437)\newline=58.31\% & &(410/826)\newline=49.63\% \\
% \hline
% Vax & (799/1706)\newline=46.83\% & (719/2363)\newline=30.42\% & (355/861)\newline=41.23\% & (410/826)\newline=49.63\% & \\
% \hline
% \end{tabular}
% \caption{Actual Templates Matched Based on Common Patterns}
% \label{tab:Inter2}
% \end{table}


\begin{table}[htb!]
 \centering
\begin{tabular}{|c | p{2cm} | p{2cm}| p{2cm} | p{2cm} | p{2cm} |}
\hline
 (n1+n2)& Arm & I386 & Mips & Sparc & Vax \\
\hline
Arm &  & (2281/3819)\newline=59.72\% & (1486/2317)\newline=64.13\% & (1475/2282)\newline=64.63\% & (799/1706)\newline=46.83\%\\
\hline
I386 & (2281/3819)\newline=59.72\% &  & (1584/2974)\newline=53.26\% & (1441/2939)\newline=49.03\% & (719/2363)\newline=30.42\%\\
\hline
Mips & (1486/2317)\newline=64.13\% & (1584/2974)\newline=53.26\% & & (838/1437)\newline=58.31\% & (355/861)\newline=41.23\% \\
\hline
Sparc & (1475/2282)\newline=64.63\% & (1441/2939)\newline=49.03\% & (838/1437)\newline=58.31\% & &(410/826)\newline=49.63\% \\
\hline
Vax & (799/1706)\newline=46.83\% & (719/2363)\newline=30.42\% & (355/861)\newline=41.23\% & (410/826)\newline=49.63\% & \\
\hline
\end{tabular}
\caption{Actual Templates Matched Based on Common Patterns}
\label{tab:Inter2}
\end{table}



From the table \ref{tab:Inter2}, it is observed that on an average 50\% of the templates share common patterns. We can note
that the results of VAX are not as good as others. We believe the reason for that is, VAX is the smallest machine considered in terms of the 
number of RTL templates parsed. 
VAX has just 125 RTL templates
and 64 patterns. In comparison, i386 has 2238 templates and 547 patterns. When comparing such a large machine with a
small machine, the number of common patterns, there by, the number of templates that match them will be reduced significantly.
We can see that i386 and VAX share a mere 34 patterns in common, which is the reason for only 30\% of the templates
to share common patterns. But if we look at machines of relatively similar size(in terms of RTL templates count), the pairs MIPS-SPARC and 
i386-ARM have about 60\% of the total templates that can be instantiated from their common patterns.



\subsection{Code\_Iterator Equivalence }

If two code iterators are found to be equivalent between two pattern files being compared, their names
were made the same. For example

i386 has

(define\_code\_iterator any\_extend [zero\_extend sign\_extend ])
and 

ARM has

(define\_code\_iterator SE [zero\_extend sign\_extend ])

both these are made equal. While comparing, a “find and replace all” is done for SE to any\_extend. Similarly, other equivalent 
code\_iterators are handled.


The above tables, list results based on strict code-iterator equivalence.
For example,

(define\_code\_iterator vqhs\_ops [smax smin plus ]) in arm.mi and

(define\_code\_iterator smaxmin [smin smax ]) in i386.mi

are considered different, i.e., not equivalent, so rtl-patterns that have these code-iterators are
considered as patterns that are not common even though the difference in very minor(a plus )in this
case. So that the figures above gives
the minimum number of patterns that are same, i.e., a safe figure. 

\section{Implications}
From the above tables, we observe that machines of similar size have common RTL patterns which can instantiate at the least
(due to strict code-iterator equivalence) around 60\% of RTL templates. So based on this observation, we can collect a
basis set of 
common RTL patterns from known machines and manage them in logical groups, like the set of patterns for arithmetic operations,
function calls, conditional branches ,etc.  This basis
set can act as a starting point for writing new machine description for machines of similar class and functionality. The tool developed, supports 
printing the patterns in 'dot' format(graphviz), which will help in easily visualizing the patterns. Hence, classifying the patterns and filling them
with machine-specific operand will be easier.


From table \ref{tab:Pat&Templates}, we observed that there is a 
significant amount of redundancy within MD files of the same machine, with the number of unique RTL patterns being 
usually in the range of one fourth of the RTL templates. So, even while writing new MD files, these redundant patterns can be factored out and listed once, 
and these patterns can be instantiated with parameters. Since a converter is available that
converts this format to existing MD file format, this is non-disruptive and new MD files can be written in a concise 
way.
  







